1. Field of the Invention
The present invention relates to parallel processing computer systems and, more particularly, to a method and apparatus for minimizing disk drive access time within a parallel processing computer system.
2. Description of the Background Art
The parallel processing computer system described in commonly assigned U.S. Pat. No. 5,581,778 issued Dec. 3, 1996 contains a control unit a plurality of processing elements, a plurality of disk drive units, an interprocessor communications (IPC) bus and a data input/output bus. The control unit is coupled, via an instruction bus, to the plurality of processing elements that are arranged in a parallel manner. Each of the processing elements is coupled to one or more disk drive storage units such that each processing element has its own source of data. The processing elements communicate with one another through the common IPC bus.
In single instruction multiple data (SIMD) operation, the control unit simultaneously broadcasts an instruction stream to all the processing elements and each processing element executes the instructions within the instruction stream in lock step. However, within each of the processing elements the data that is operated upon by the instruction is different and generally recalled from the local disk drive unit. Although all of the processing elements receive the same instruction, not all of the processing elements may be enabled to execute instructions from that instruction stream. As such, the control unit may selectively disable one or more of the processing elements that will not participate in the processing of the current instruction stream.
For those processing elements that are enabled, each element independently requests information from its associated disk drive.
A disk drive access consists of a disk arm seek to an appropriate disk cylinder/track, combined with a read or write (r/w) operation for a particular disk sector in the selected cylinder/track. The time required to complete a disk access is approximately equal to a worst case seek operation, i.e., move the disk arm the distance equal to the radius of the disk. This duration dominates the time to complete a read or write operation for a given disk drive. As such, the execution time of a disk access is data dependent, e.g., the access depends on the sector address relative to the present location of the disk arm. Thus, a disk access requires a variable length of time to be performed on each of the processing elements.
To ensure lock step instruction execution as required in SIMD mode, the control unit broadcasts the next disk access instruction to the processing elements only after they have all completed the current accesses. Therefore, each disk access instruction takes as long as the slowest processing element requires to complete the access request. If some of the processing elements are disabled for a given disk access, they remain idle until each enabled processing element has completed a disk access. When the control unit broadcasts many disk access requests, the overhead associated with each processing element waiting for the longest access to be complete can be significant. For certain applications, a fixed disk input/output rate must be sustained, e.g., video-on-demand applications. As such, a known set of disk access operations must be completed during a fixed interval of time.
More formally, suppose N disk access requests are queued for each interval of time for at least one disk. Let T.sub.i.sup.k represent the time required to complete a disk access i, 0.ltoreq.i&lt;N, for processing element k. In SIMD mode, the execution time of a sequence of disk accesses is expressed as ##EQU1## (T.sub.i.sup.k). If the time for a read or write operation equals .tau..sub.r/w,and the worst case time for a seek operation is .tau..sub.seek, then the worst case total execution time is N.times..tau..sub.r/w +N.times..tau..sub.seek. Because each processing element waits for the longest disk access to complete before executing the next instruction, a worst case seek time for all processing elements occurs whenever a worst case seek occurs in any one of the processing elements within the parallel processing computer system. Consequently, to avoid asynchronous operation of the processing elements all the processing elements wait for the longest amount of time expected for a seek operation. As such, many of the processors may wait for long periods of time while waiting for the expected longest period of time to expire.
Therefore, a need exists in the art for a method and apparatus that minimizes the disk access time for a parallel processing computer system.